package com.chj.dfs.class04;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

public class Code07_Permutations {

	public static List<List<Integer>> permute(int[] nums) {
		int len = nums.length;
		// 使用一个动态数组保存所有可能的全排列
		List<List<Integer>> res = new ArrayList<>();
		if (len == 0) {
			return res;
		}

		boolean[] used = new boolean[len];
		Deque<Integer> path = new ArrayDeque<>(len);

		dfs(nums, len, 0, path, used, res);
		return res;
	}

	private static void dfs(int[] nums, int len, int depth, Deque<Integer> path, boolean[] used,
			List<List<Integer>> res) {
		if (depth == len) {
			res.add(new ArrayList<>(path));
			return;
		}

		for (int i = 0; i < len; i++) {
			if (!used[i]) {
				path.addLast(nums[i]);
				used[i] = true;

				System.out.println("  递归之前 => " + path);
				dfs(nums, len, depth + 1, path, used, res);

				used[i] = false;
				path.removeLast();
				System.out.println("递归之后 => " + path);
			}
		}
	}

	public static List<List<Integer>> permute02(int[] nums) {
		// 首先是特判
		int len = nums.length;
		// 使用一个动态数组保存所有可能的全排列
		List<List<Integer>> res = new ArrayList<>();

		if (len == 0) {
			return res;
		}

		boolean[] used = new boolean[len];
		List<Integer> path = new ArrayList<>();

		dfs02(nums, len, 0, path, used, res);
		return res;
	}

	private static void dfs02(int[] nums, int len, int depth, List<Integer> path, boolean[] used,
			List<List<Integer>> res) {
		if (depth == len) {
			// 3、不用拷贝，因为每一层传递下来的 path 变量都是新建的
			res.add(path);
			return;
		}

		for (int i = 0; i < len; i++) {
			if (!used[i]) {
				// 1、每一次尝试都创建新的变量表示当前的"状态"
				List<Integer> newPath = new ArrayList<>(path);
				newPath.add(nums[i]);

				boolean[] newUsed = new boolean[len];
				System.arraycopy(used, 0, newUsed, 0, len);
				newUsed[i] = true;

				dfs02(nums, len, depth + 1, newPath, newUsed, res);
				// 2、无需回溯
			}
		}
	}

	public static void main(String[] args) {
		{
			int[] nums = { 1, 2, 3 };
			List<List<Integer>> lists = permute(nums);
			System.out.println(lists);
		}

		{
			int[] nums = { 1, 2, 3 };
			List<List<Integer>> lists = permute02(nums);
			System.out.println(lists);
		}
	}
}
